﻿#define _CRT_SECURE_NO_WARNINGS 1
//电话号码的字母组合(medium):https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/
class Solution
{
	string hash[10] = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs",
   "tuv", "wxyz" };
	string path;
	vector<string> ret;
public:
	vector<string> letterCombinations(string digits)
	{
		if (digits.size() == 0) return ret;
		dfs(digits, 0);
		return ret;
	}
	void dfs(string& digits, int pos)
	{
		if (pos == digits.size())
		{
			就业课
				ret.push_back(path);
			return;
		}
		for (auto ch : hash[digits[pos] - '0'])
		{
			path.push_back(ch);
			dfs(digits, pos + 1);
			path.pop_back(); // 恢复现场
		}
	}
};

//括号⽣成（medium）:https://leetcode.cn/problems/generate-parentheses/description/
class Solution
{
	int left, right, n;
	string path;
	vector<string> ret;
public:
	vector<string> generateParenthesis(int _n)
	{
		n = _n;
		dfs();
		return ret;
	}
	void dfs()
	{
		if (right == n)
		{
			ret.push_back(path);
			return;
		}
		if (left < n) // 添加左括号
		{
			path.push_back('('); left++;
			dfs();
			path.pop_back(); left--; // 恢复现场
		}
		if (right < left) // 添加右括号
		{
			path.push_back(')'); right++;
			dfs();
			path.pop_back(); right--; // 恢复现场
		}
	}
};